#include <stdio.h>

/*
	结合插入排序实现二分查找。
*/

void InsertionSort(int array[], int n)
{
	int i, j, k, temp;
	for (i = 1; i < n; i++)
	{
		for (j = i - 1; j >= 0; j--)
		{
			if (array[j] < array[i])
			{
				temp = array[i];
				break;
			}
		}
		for (k = i; k > j; k--)
		{
			array[k] = array[k - 1];
		}
		array[j + 1] = temp;
	}
}

int BinarySearch(int data, int array[], int bottom, int top)
{
	int left = bottom, right = top;
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (data == array[mid])
		{
			return mid;
		}
		if (data > array[mid])
		{
			left = mid + 1;
		}
		if (data < array[mid])
		{
			right = mid - 1;
		}
	}
	return -1;
}

int main()
{
	int array[] = {12, 151, 42, 532, 754, 54, 842};
	int n = sizeof(array) / sizeof(int);
	InsertionSort(array, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", array[i]);
	}
	putchar('\n');
	printf("%d\n", BinarySearch(200, array, 0, n));
	return 0;
}
